翻訳と辞書
Words near each other
・ Facilitation board (economics)
・ Facilitator
・ Facilities engineering
・ Facilities of the Canadian Pacific Railway
・ Facilities on the Mass Rapid Transit (Singapore)
・ Facilities Protection Service
・ Facility
・ Facility condition assessment
・ Facility condition index
・ Facility Credit Guarantee Program
・ Facility for Airborne Atmospheric Measurements
・ Facility for Antiproton and Ion Research
・ Facility for Rare Isotope Beams
・ Facility ID
・ Facility information model
Facility location problem
・ Facility management
・ Facility operations
・ Facility Registry System
・ Facility Solutions Group
・ Facimiech, Lesser Poland Voivodeship
・ Facinas
・ Facinet Bangoura
・ Facinet Keita
・ Facing
・ Facing (machining)
・ Facing (retail)
・ Facing (sewing)
・ Facing a Miracle
・ Facing Africa


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Facility location problem : ウィキペディア英語版
Facility location problem

The facility location problem, also known as location analysis or ''k''-center problem, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to cluster analysis.
==Minimum facility location==

A simple facility location problem is the Weber problem, in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted sum of distances from a given set of point sites. More complex problems considered in this discipline include the placement of multiple facilities, constraints on the locations of facilities, and more complex optimization criteria.
In a basic formulation, the facility location problem consists of a set of potential facility sites ''L'' where a facility can be opened, and a set of demand points ''D'' that must be serviced. The goal is to pick a subset ''F'' of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities.
The facility location problem on general graphs is NP-hard to solve optimally, by reduction from (for example) the set cover problem. A number of approximation algorithms have been developed for the facility location problem and many of its variants.
Without assumptions on the set of distances between clients and sites (in particular, without assuming that the distances satisfy the triangle inequality), the problem is known as non-metric facility location and can be approximated to within a factor O(log ''n''). This factor is tight, via an approximation-preserving reduction from the set cover problem.
If we assume distances between clients and sites are undirected and satisfy the triangle inequality, we are talking about a metric facility location (MFL) problem. The MFL is still NP-hard and hard to approximate within factor better than 1.463. The currently best known approximation algorithm achieves approximation ratio of 1.488.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Facility location problem」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.